package leetcode_top;
import java.util.*;
import org.junit.*;
public class Ex15 {
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            int len = nums.length;
            if (len < 3) return new ArrayList<>();
            List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(nums);
            int lo = 0, hi, tar, mid, sum;
            for (; lo < len - 2; lo++) {
                if (nums[lo] > 0) return res;
                if (lo >= 1 && nums[lo] == nums[lo - 1]) {
                    continue;
                }
                //遍历得到中间和右边界
                mid = lo + 1;
                hi = len - 1;
                tar = -nums[lo];
                while (mid < hi) {
                    if ((sum = nums[mid] + nums[hi]) == tar) {
                        res.add(Arrays.asList(nums[lo],nums[mid],nums[hi]));
                        while (mid < hi && nums[mid + 1] == nums[mid]) mid++;
                        while (mid < hi && nums[hi - 1] == nums[hi]) hi--;
                        mid++;
                    } else if (sum > 0) {
                        hi--;
                    } else {
                        mid++;
                    }
                }
            }
            
            return res;
        }
    
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{-1,0,1,2,-1,-4};
        System.out.println(s.threeSum(nums));
    }
}
